package main

func main() {

}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var sum int

//中序遍历
/**
 * @Description:全局变量sum
 */
func rangeSumBST(root *TreeNode, low int, high int) int {
	sum = 0
	return inorder(root, low, high)
}

/**
 * @Description:局部变量sum
 */
func rangeSumBST2(root *TreeNode, low int, high int) int {
	sum := 0
	nums := inorder2(root)
	for i := 0; i < len(nums); i++ {
		if num := nums[i]; num >= low && num <= high {
			sum += num
		}
	}
	return sum
}

func inorder2(root *TreeNode) []int {
	nums := make([]int, 0)
	if root != nil {
		nums = append(nums, inorder2(root.Left)...)
		nums = append(nums, root.Val)
		nums = append(nums, inorder2(root.Right)...)
	}
	return nums
}

/**
 * @Description: 中序遍历
 */
func inorder(root *TreeNode, low, high int) int {
	if root != nil {
		inorder(root.Left, low, high)
		val := root.Val
		if val >= low && val <= high {
			sum += val
		} else if val > high {
			return sum
		}
		inorder(root.Right, low, high)
	}
	return sum
}
